% =========================================================
% PREDICADOS AUXILIARES
% =========================================================

%caracter(?A)
caracter(A) :- member(A, [0,1]).

%cadena(?L)
cadena(L) :- var(L)    -> (length(L, _), maplist(caracter, L));
             nonvar(L) -> maplist(caracter, L).

%cadenaDeLongMax(?L, +LongMax)
cadenaDeLongMax(L, LongMax) :- nonvar(LongMax), between(0, LongMax, N), length(L, N), cadena(L).

%diferenciaCaracteres(+C1, +C2, -R)
diferenciaCaracteres(C1, C2, R) :- caracter(C1), caracter(C2), R is abs(C1 - C2).

%diferenciaEntreCadenas(+L1, +L2, -Dif)
diferenciaEntreCadenas(L1, L2, Dif) :- maplist(diferenciaCaracteres, L1, L2, Dif).

%cantidadDiferencias(+L, -Cant)
cantidadDiferencias(L, Cant) :- sumlist(L, Cant).

%prefijo(+L1, +L2, -Pref)
prefijo(L1, L2, Pref) :- append(Pref, _, L1), append(Pref, _, L2).

%prefijoComun(+L1, +L2, -Pref)
mayorPrefijo(L1, L2, Pref) :- 	prefijo(L1, L2, Pref), length(Pref, LongPref), 
								forall(prefijo(L1, L2, OtroPref), (length(OtroPref, LongOtroPref), 
								LongPref >= LongOtroPref)).

%sumaLongCadenasSacandoPrefijo(+S, +T, +Pref, -Sum)
sumaLongCadenasSacandoPrefijo(S, T, Pref, Sum) :- 	append(Pref, RestanteS, S), append(Pref, RestanteT, T), 
													append(RestanteS, RestanteT, L), length(L, Sum).

% El predicado edicion es verdadero si existe una edición de T en S con distancia D. Para validar esto, utiliza los
% predicados cambiarCaracter, sacarCaracter y agregarCaracter dependiendo de la diferencia de longitud de las cadenas.

%edicion(+S, +T, +D)
edicion(S, S, 0).
edicion(S, T, D) :- D > 0, length(S, LongS), length(T, LongT), LongS=LongT, S \= T, cambiarCaracter(T, T1), 
					Dm1 is D - 1, edicion(S, T1, Dm1).
edicion(S, T, D) :- D > 0, length(S, LongS), length(T, LongT), LongS<LongT, sacarCaracter(T, T1), 
					Dm1 is D - 1, edicion(S, T1, Dm1).
edicion(S, T, D) :- D > 0, length(S, LongS), length(T, LongT), LongS>LongT, agregarCaracter(T, T1), 
					Dm1 is D - 1, edicion(S, T1, Dm1).

% El predicado minimaEdicion se divide en casos según la instanciación de D: 
% - Si la distancia no se encuentra instanciada se instancia D con un valor entre 0 y la longitud de S sumada a la de T.
%	El primer valor de D que cumpla con el predicado edición será la distancia mínima y, por lo tanto, no se deberá
%	volver sobre esa rama y se utiliza un cut.
% - Si la distancia D está instanciada se debe chequear que existe una edición con distancia D y que dicha edición sea
%	mínima. Para ello se evalúa el predicado edicion con la distancia D y para cada distancia menor a D se verifica que
%	no exista una edición con esa distancia. Si estas dos condiciones valen no se debe seguir explorando dicha rama y,
%	por lo tanto, se corta la ejecución de la misma.

%minimaEdicion(+S, +T, ?D)
minimaEdicion(S, T, 0) :- 	edicion(S, T, 0).
minimaEdicion(S, T, D) :- 	ground(D), D > 0, edicion(S, T, D), Dm1 is D-1, 
							forall(between(0, Dm1, DistMenor), not(edicion(S, T, DistMenor))), !.
minimaEdicion(S, T, D) :- 	not(ground(D)), length(S, LongS), length(T, LongT), SumLong is LongS+LongT, 
							between(0, SumLong, D), edicion(S, T, D), !.

%complemento(+C, -Comp)
complemento(C, Comp) :- caracter(C), Comp is abs(C-1).

%agregarCaracter(+S, -T)
agregarCaracter(S, T) :- caracter(C), append(Parte1, Parte2, S), append([Parte1, [C], Parte2], T).

%sacarCaracter(+S, -T)
sacarCaracter(S, T) :- append([Parte1, [_], Parte2], S), append(Parte1, Parte2, T).

%cambiarCaracter(+S, -T)
cambiarCaracter(S, T) :- append([Parte1, [C], Parte2], S), complemento(C, C1), append([Parte1, [C1], Parte2], T).

% =========================================================
% PREDICACADOS DE DISTANCIAS
% =========================================================

% El predicado distHam usa diferenciaEntreCadenas que es verdadero si Dif es la lista que tiene un 1 en las posiciones
% en que S difiere de T y un 0 en las posiciones en las que los caracteres son iguales. Habiendo obtenido las 
% diferencias entre S y T, las mismas se cuentan usando cantidadDiferencias.

%distHam(+S, ?T, ?D)
distHam(S, T, D) :- diferenciaEntreCadenas(S, T, Dif), cantidadDiferencias(Dif, D).

% El predicado distPref se divide en dos casos:
% - Cuando la distancia D está instanciada la cadena T, que puede o no venir instanciada, debe tener una longitud
%	máxima que se corresponde con la suma de la longitud de S y la distancia D. Por lo tanto se usa cadenaDeLongMax
%	para instanciar o chequear que T sea una cadena de longitud menor o igual a LongMaxT. 
% - Cuando la distancia D no está instanciada, en principio, la longitud de T no está acotada por lo que sólo se chequea
%	que T sea una cadena válida si está instanciada o se instancia con el predicado cadena.
%
% En ambos casos, una vez que se tiene instanciada T, se obtiene el mayor prefijo común entre S y T usando mayorPrefijo
% y luego con el predicado sumaLongCadenasSacandoPrefijo se obtiene la suma de las longitudes de S y T sacando dicho
% prefijo.

%distPref(+S, ?T, ?D)
distPref(S, T, D) :- 	ground(D), cadena(S), length(S, LongS), LongMaxT is LongS + D, cadenaDeLongMax(T, LongMaxT),
						mayorPrefijo(S, T, Pref), sumaLongCadenasSacandoPrefijo(S, T, Pref, D).
distPref(S, T, D) :- 	not(ground(D)), cadena(S), cadena(T), 
						mayorPrefijo(S, T, Pref), sumaLongCadenasSacandoPrefijo(S, T, Pref, D). 

% Al igual que distPref, distEd se divide en dos casos, dependiendo de la instanciación de D, para limitar la 
% longitud de T en caso de que la distancia esté instanciada. Luego, en ambos casos, se utiliza el predicado 
% minimaEdicion una vez que se tiene instanciada T. La explicación de minimaEdicion se puede encontrar junto a la
% definición del predicado.

%distEd(+S, ?T, ?D)
distEd(S, T, D) :- ground(D), cadena(S), length(S, LongS), LongMaxT is LongS + D, cadenaDeLongMax(T, LongMaxT),
					minimaEdicion(S, T, D).
distEd(S, T, D) :- not(ground(D)), cadena(S), cadena(T), minimaEdicion(S, T, D).


% =========================================================
% TESTS
% =========================================================
:- begin_tests(distham).

test(distham_1, [fail]) :- distHam([], [0], _).

test(distham_2, [fail]) :- distHam([prueba], [prueba], _).

test(distham_3, [fail]) :- distHam([1,0], [0], _).

test(distham_4, [fail]) :- distHam([1,0], [0,1], 1).

test(distham_5, [nondet]) :- distHam([0,1], [0,1], N), N == 0.

test(distham_6, [nondet]) :- distHam([0,1,0], [0,0,1], N), N == 2.

test(distham_7, [nondet]) :- 
	findall((X,Y,N), distHam([0,1,0], [X,Y,1], N), Res),
	length(Res, 4),
	member((0,1,1), Res), 
	member((0,0,2), Res), 
	member((1,1,2), Res),
	member((1,0,3), Res).

test(distham_8, [nondet]) :- 
	findall(X, distHam([0,1,0], X, 2), Res),
	length(Res,3),
	member([0,0,1], Res), 
	member([1,1,1], Res), 
	member([1,0,0], Res).
	
test(distham_9, [nondet]) :-
	findall((L,N), distHam([1,0], L, N), Res),
	length(Res, 4),
	member(([0,0],1), Res),
	member(([0,1],2), Res),
	member(([1,0],0), Res),
	member(([1,1],1), Res).
	
:- end_tests(distham).

:- begin_tests(distpref).
	
	test(distpref_1, [fail]) :- distPref([prueba],_,_).
	
	test(distpref_2, [fail]) :- distPref([1,1,1],[0,1,1,1],N), N == 6.
	
	test(distpref_3, [fail]) :- distPref([0,1],[_,prueba|_],_).
	
	test(distpref_4, [nondet]) :- distPref([1,1,1],[],N), N == 3.

	test(distpref_5, [nondet]) :- distPref([0,1,1],[0,1,1,1],N), N == 1.
	
	test(distpref_6, [nondet]) :- distPref([0,1,1],[0,0,1,1],N), N == 5.
	
	test(distpref_7, [nondet]) :- 
		findall((X,Y,N), distPref([0,1,1],[0,1,X,Y],N), Res),
		length(Res, 4),
		member((1,0,1), Res),
		member((1,1,1), Res),
		member((0,0,3), Res),
		member((0,1,3), Res).
		
	test(distpref_8, [nondet]) :-
		findall(X, distPref([0,1,1],X,2), Res),
		length(Res, 6),
		member([0], Res),
		member([0,1,1,0,0], Res),
		member([0,1,1,0,1], Res),
		member([0,1,1,1,0], Res),
		member([0,1,1,1,1], Res),
		member([0,1,0], Res).
		
	test(distpref_9, [nondet]) :-
		findall((X,Y,N), distPref([0,1,0], [X,Y], N), Res),
		length(Res, 4),
		member((0,0,3), Res),
		member((0,1,1), Res),
		member((1,0,5), Res),
		member((1,1,5), Res).
		
	test(distpref_10, [nondet]) :-
		findall(X, distPref([],X,1), Res),
		length(Res, 2),
		member([0], Res),
		member([1], Res).
		
	test(distpref_11, [nondet]) :-
		findall(XS, distPref([1,0],[1|XS], 2), Res),
		length(Res, 5),
		member([0,0,0], Res),
		member([0,0,1], Res),
		member([0,1,0], Res),
		member([0,1,1], Res),
		member([1], Res).

:- end_tests(distpref).

:- begin_tests(disted).

test(disted_1, [fail]) :- distEd([prueba],_,_).

test(disted_2, [fail]) :- distEd([0,1],[_,prueba|_],_).

test(disted_3, [fail]) :- distEd([0,1],[_,0|_],0).

test(disted_4, [nondet]) :- distEd([0,1],[X,1|XS],0), XS = [], X = 0.

test(disted_5, [nondet]) :- distEd([0,0,1,1],[1,1,0],N), N == 3.

test(disted_6, [nondet]) :- 
		findall((X,Y,N), distEd([0,0,1],[1,1,X,Y],N), Res),
		length(Res, 4),
		member((0,0,3), Res),
		member((0,1,2), Res),
		member((1,0,3), Res),
		member((1,1,3), Res).
		
test(disted_7, [nondet]) :-
		findall(XS, distEd([0,1,1,1],[1|XS],2), Res),
		length(Res, 19),
		member([1], Res),
		member([0,1], Res),
		member([1,0], Res),
		member([0,1,1], Res),
		member([1,0,1], Res),
		member([1,1,0], Res),
		member([0,0,1,1], Res),
		member([0,1,0,1], Res),
		member([0,1,1,0], Res),
		member([1,0,1,1], Res),
		member([1,1,0,1], Res),
		member([1,1,1,0], Res),
		member([1,1,1,1], Res),
		member([0,0,1,1,1], Res),
		member([0,1,0,1,1], Res),
		member([0,1,1,0,1], Res),
		member([0,1,1,1,0], Res),
		member([0,1,1,1,1], Res),
		member([1,0,1,1,1], Res).
		
test(disted_8, [nondet]) :-
		findall(XS, distEd([0,1],XS,1), Res),
		length(Res, 8),
		member([0], Res),
		member([1], Res),
		member([0,0], Res),
		member([1,1], Res),
		member([0,1,0], Res),
		member([0,1,1], Res),
		member([0,0,1], Res),
		member([1,0,1], Res).
		
test(disted_9, [nondet]) :- distEd([0,1],XS,0), XS = [0,1].

test(disted_10, [nondet]) :- distEd([0,1],[],N), N = 2.

test(disted_11, [nondet]) :- distEd([],[1,0,1],N), N = 3.

:- end_tests(disted).
% =========================================================
